//在一个由 '0' 和 '1' 组成的二维矩阵内，找到只包含 '1' 的最大正方形，并返回其面积。
//
//
//
// 示例 1：
//
//
//输入：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"]
//,["1","0","0","1","0"]]
//输出：4
//
//
// 示例 2：
//
//
//输入：matrix = [["0","1"],["1","0"]]
//输出：1
//
//
// 示例 3：
//
//
//输入：matrix = [["0"]]
//输出：0
//
//
//
//
// 提示：
//
//
// m == matrix.length
// n == matrix[i].length
// 1 <= m, n <= 300
// matrix[i][j] 为 '0' 或 '1'
//
// Related Topics 数组 动态规划 矩阵 👍 1019 👎 0

package leetcode.editor.cn;

@SuppressWarnings("all")
//Java：最大正方形
public class 最大正方形 {
    public static void main(String[] args) {
        Solution solution = new 最大正方形().new Solution();
        // TO TEST
        char[][] matrix = {
                {'1', '0', '1', '0', '0'},
                {'1', '0', '1', '1', '1'},
                {'1', '0', '1', '1', '1'},
                {'1', '0', '0', '1', '0'}
        };
        System.out.println(solution.maximalSquare(matrix));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int maximalSquare(char[][] matrix) {
            int line = matrix.length;
            int clumn = matrix[0].length;
            int max = 0;
            for (int i = 0; i < line; i++) {
                for (int j = 0; j < clumn; j++) {
                    if (i == 0 || j == 0 ) {
                        max = Math.max(max, matrix[i][j] - '0');
                    } else if (matrix[i][j] == '1') {
                        char c = (char) (Math.min(Math.min(matrix[i - 1][j - 1], matrix[i - 1][j]), matrix[i][j - 1]) + 1);
                        matrix[i][j] = c;
                        max = Math.max(max, c - '0');
                    }
                }
            }

            return max * max;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)


}
